02-线性结构 2 一元多项式的乘法与加法运算
题目要求
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分 2 行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。
输出格式:
输出分 2 行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
输入样例:
1
2
| 4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
|
输出样例:
1
2
| 15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
|
解题思路：
根据输入样例，多项式均是以指数递减的方式输入，可用动态数组和单链表来表示多项式，本题采用单链表来表示。链表结构如下
1
2
3
4
5
6
| typedef struct PolyNode *Polynomial;
struct PolyNode {
int coef;
int expon;
Polynomial link;
}
|
按照题目要求搭建程序框架：
1
2
3
4
5
6
7
8
9
| int main()
{
读取多项式 1
读取多项式 2
乘法运算并输出
加法运算并输出
return 0;
}
|
因此，需要设计读取，加法和乘法运算，输出四个功能的函数。
① 读取函数
根据题目的输入样例，设计读取函数，由于链表中结点链接到链表中从操作频繁，增加设计一个链接函数 Attach()，方便操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
void Attach(int c, int e, Polynomial *pRear)
{
Polynomial t = new Polynomial();
t->coef = c;
t->expon = e;
t->link = NULL;
(*pRear)->link = t;
*pReal = t;
}
Polynomial ReadPoly()
{
Polynomial P = new Polynomial();
Polynomial Rear, t;
P->link = NULL;
Rear = P;
int n, c, e;
cin >> n;
while(n--)
{
cin >> c >> e;
Attach(c,e,&Rear);
}
t = P;
P = P->link;
free(t);
return P;
}
|
② 多项式相加函数
两个多项式相加，就是逐项比较两个链表每一项，将指数相同的项系数相加得到新的项，指数较大的项链接到结果链表后并将指针向后移，直到其中一个链表遍历完，将另一链表剩余部分全部连接到结果链表后。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
Polynomial AddPoly(Polynomial P1, Polynomial P2)
{
Polynomial Rear, t1, t2, t;
t1 = P1;
t2 = P2;
Polynomial P = new PolyNode;
P->link = NULL;
Rear = P;
while(t1 && t2)
{
if(t1->expon == t2->expon)
{
int sum = t1->coef + t2->coef;
if(sum != 0)
{
Attach(sum,t1->expon,&Rear);
t1 = t1->link;
t2 = t2->link;
}
else
{
t1 = t1->link;
t2 = t2->link;
}
}
else if(t1->expon > t2->expon)
{
Attach(t1->coef,t1->expon,&Rear);
t1 = t1->link;
}
else if(t1->expon < t2->expon)
{
Attach(t2->coef,t2->expon,&Rear);
t2 = t2->link;
}
}
for(;t1;t1=t1->link) Attach(t1->coef,t1->expon,&Rear);
for(;t2;t2=t2->link) Attach(t2->coef,t2->expon,&Rear);
Rear->link = NULL;
t = P;
P = P->link;
free(t);
return P;
}
|
③ 多项式相乘函数
两个多项式相乘较为麻烦，可以分解为两个主要步骤：
<1> 将乘法运算转变为加法运算
将 P1 当前项（ci ,ei ) 乘 P2 多项式，再加到结果多项式里
1
2
3
4
5
6
7
8
| t1 = P1; t2 = P2;
Polynomial P = new Polynomial();
Rear = P;
while(t2)
{
Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
t2 = t2->link;
}
|
<2> 逐项插入
将 P1 当前项（c1i ,e1i ) 乘 P2 当前项（c2i ,e2i )，并插入到结果多项式中。关键是要找到插入位置。其中结果多项式的初始位置可由 P1 的第一项乘以 P2 获得。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| t1 = t1->link;
while(t1)
{
t2 = P2;
Rear = P;
while(t2)
{
c = t1->coef * t2->coef;
e = t1->expon + t2->expon;
while (Rear->link && Rear->link->expon > e)
{
Rear = Rear->link;
}
if(Rear->link && Rear->link->expon == e)
{
if(Rear->link->coef+c)
{
Rear->link->coef+=c;
}
else
{
t = Rear->link;
Rear->link = t->link;
free(t);
}
}
else
{
t = new PolyNode;
t->coef = c;
t->expon = e;
t->link = Rear->link;
Rear->link = t;
Rear = Rear->link;
}
t2 = t2->link;
}
t1 = t1->link;
}
|
④ 输出函数
要按照输出样例的格式输出，注意到输出的多项式每组系数和指数间都有空格，每个项之间也有空格，但是首尾没有空格。
可以把每组数据看作，“空格+系数+指数”，但是第一项没有空格，因此可以设置一个 flag 来控制输出，flag 初始值为 0，在执行一步输出操作后置为 1，只有 flag 为 1 时才输出空格。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void PrintPoly(Polynomial P)
{
bool flag = 0;
if(!P)
{
cout << "0 0" << endl;
}
else
{
while(P)
{
if(!flag)
flag = 1;
else
cout << " ";
cout << P->coef << " " << P->expon;
P = P->link;
}
}
cout << endl;
}
|
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
| #include<bits/stdC++.h>
using namespace std;
typedef struct PolyNode *Polynomial;
struct PolyNode {
int coef;
int expon;
Polynomial link;
};
void Attach(int c, int e, Polynomial *pRear);
Polynomial ReadPoly();
Polynomial AddPoly(Polynomial P1, Polynomial P2);
Polynomial MultPoly(Polynomial P1, Polynomial P2);
void PrintPoly(Polynomial P);
int main()
{
Polynomial P1, P2, Pa, Pm;
P1 = ReadPoly();
P2 = ReadPoly();
Pa = AddPoly(P1,P2);
Pm = MultPoly(P1,P2);
PrintPoly(Pm);
PrintPoly(Pa);
return 0;
}
void Attach(int c, int e, Polynomial *pRear)
{
Polynomial t = new PolyNode;
t->coef = c;
t->expon = e;
t->link = NULL;
(*pRear)->link = t;
*pRear = t;
}
Polynomial ReadPoly()
{
Polynomial P = new PolyNode;
Polynomial Rear, t;
P->link = NULL;
Rear = P;
int n, c, e;
cin >> n;
while(n--)
{
cin >> c >> e;
Attach(c,e,&Rear);
}
t = P;
P = P->link;
free(t);
return P;
}
Polynomial AddPoly(Polynomial P1, Polynomial P2)
{
Polynomial Rear, t1, t2, t;
t1 = P1;
t2 = P2;
Polynomial P = new PolyNode;
P->link = NULL;
Rear = P;
while(t1 && t2)
{
if(t1->expon == t2->expon)
{
int sum = t1->coef + t2->coef;
if(sum != 0)
{
Attach(sum,t1->expon,&Rear);
t1 = t1->link;
t2 = t2->link;
}
else
{
t1 = t1->link;
t2 = t2->link;
}
}
else if(t1->expon > t2->expon)
{
Attach(t1->coef,t1->expon,&Rear);
t1 = t1->link;
}
else if(t1->expon < t2->expon)
{
Attach(t2->coef,t2->expon,&Rear);
t2 = t2->link;
}
}
for(;t1;t1=t1->link) Attach(t1->coef,t1->expon,&Rear);
for(;t2;t2=t2->link) Attach(t2->coef,t2->expon,&Rear);
Rear->link = NULL;
t = P;
P = P->link;
free(t);
return P;
}
Polynomial MultPoly(Polynomial P1, Polynomial P2)
{
int c, e;
if(!P1 || !P2) return NULL;
Polynomial t, t1, t2, Rear;
t1 = P1; t2 = P2;
Polynomial P = new PolyNode;
P->link = NULL;
Rear = P;
while(t2)
{
Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
t2 = t2->link;
}
t1 = t1->link;
while(t1)
{
t2 = P2;
Rear = P;
while(t2)
{
c = t1->coef * t2->coef;
e = t1->expon + t2->expon;
while (Rear->link && Rear->link->expon > e)
{
Rear = Rear->link;
}
if(Rear->link && Rear->link->expon == e)
{
if(Rear->link->coef+c)
{
Rear->link->coef+=c;
}
else
{
t = Rear->link;
Rear->link = t->link;
free(t);
}
}
else
{
t = new PolyNode;
t->coef = c;
t->expon = e;
t->link = Rear->link;
Rear->link = t;
Rear = Rear->link;
}
t2 = t2->link;
}
t1 = t1->link;
}
t2 = P;
P = P->link;
free(t2);
return P;
}
void PrintPoly(Polynomial P)
{
bool flag = 0;
if(!P)
{
cout << "0 0";
}
else
{
while(P)
{
if(!flag)
flag = 1;
else
cout << " ";
cout << P->coef << " " << P->expon;
P = P->link;
}
}
cout << endl;
}
|
微信
支付宝
